1. Field of the Invention
The present invention relates to a delay time verifier for logic circuits and particularly relates to a delay time verifier which generates a graph theory expression of a logic circuit and verifies the delay of that logic circuit using information for delay time verification represented by the logic in such graph theory model.
2. Description of the Related Art
Conventional delay time verification methods for a logic circuit will be described below taking an example where a simple logic circuit model shown in FIG. 2 operates with the signal waveform as shown in FIG. 3.
In FIG. 2, a device 230 receives as input the signal from an input terminal 210 and, 1 ns later, outputs the same signal as the input signal to a path 250. A device 240 is an OR circuit which receives, as two inputs, the signals from the path 250 and the input terminal 210 and outputs their logical OR to an output terminal 220 with a delay time of 0 (ns). Other operations are also supposed to have a delay time of 0.
As shown in FIG. 3, the signal at the input terminal 210 rises at the time 0 ns and falls at the time 2 ns. For the path 250, the same signal as the input terminal 210 appears with a delay of 1 ns. In other words, the signal at the path 250 rises at the time 1 ns and falls at the time 3 ns. The signal at the output terminal 220 is the logical OR of the signal at the path 250 and the signal at the input terminal 210 and therefore rises at the time 0 ns and falls at the time 3 ns.
One of the methods for delay time verification in such a logic circuit model is application of the graph theory. It is a known theory where a logic circuit is expressed as a validness graph according to certain rules so that various processing regarding characteristics of that logic circuit can be made easily. Details of the graph theory are described, for example, in known literature including (1) R. J. Wilson, translated by Sinji Saito and Takao Nishiseki, "Introduction to Graph Theory", Kindai Kagakusha and (2) Masao Iri and Isao Shirakawa, "Seminar of Graphic Theory (Foundation and Application)".
FIG. 4 shows the circuit model of FIG. 2 expressed as a graph according to the graph theory. Specifically, it is a validness graph which has external terminals and other device terminals as nodes p to v, and is provided with arcs a to g whose directions are the flow of signals between the applicable nodes. These arcs "a" to "g" have their delay time as their weight. The delay time is provided for each rise or fall type (R/F type) for the start point and end point nodes for every arc. If there is no delay time, the weight is expressed as "x" (undefined).
In FIG. 4, which represents a validness graph of the circuit model shown in FIG. 2, the arc "a" corresponds to the signal path between the input terminal 210 and the input terminal of the device 230, the arc "b" to the internal signal path of the device 230, the arc "c" to the signal path 250, the arc "d" to the internal signal path of the device 240, the arc "e" to the signal path between the output terminal of the device 240 and the output terminal 220, arc "f" to the signal path between the input terminal 210 and the input terminal of the device 240, and the arc "g" to the internal signal path of the device 240. The arc "a" has its start point node at p and end point node at q; the arc "b" has its start point node at q and end point node at r; the arc "c" has its start point node at r and end point node at s . . . . FIG. 5 shows correspondence between such circuit model and the validness graph.
The weight of an arc is the delay time provided for each R/F type of the start point and end point nodes. FIG. 6 shows the weights given to the arcs for the operation waveform in FIG. 3. In FIG. 6, "0" and "1" represent the delay time in ns and "X" means that the delay time is undefined.
In general, a combination of rise (R) and fall (F) of the signal for the start point node and end point node (hereinafter simply referred to as start and end) for an arc is, as shown in FIG. 6, one of four possibilities: start with R and end with R (R/R), start with R and end with F (R/F), start with F and end with R (F/R) and start with F and end with F (F/F). However, in the example shown in FIGS. 2 and 3, it is not necessary to consider R/F and F/R for the arcs and they are treated as "undefined". Other two combinations R/R and F/F are respectively provided with a delay time as the 5 weight according to the example in FIG. 3.
In actual delay verification, information shown in FIGS. 4 and 6 is in advance stored in a verified model information file. For both of the first series of paths (arc "a" .fwdarw. "b" .fwdarw. "c" .fwdarw. "d" .fwdarw. "e") and the second series of paths (arc "f" .fwdarw. "g" .fwdarw. "e"), the weight is determined for each of R/F type for the start and end of every arc as in FIG. 6 so that the delay time of each series of paths can be obtained as the sum of the determined weights.
The delay time for the processes from the input terminal 210 to the output terminal 220 in the circuit model of FIG. 2 is, as obviously understood from the waveform example of FIG. 3, 0 ns corresponding to the delay time of the lower route (arc "f" .fwdarw. "g") in FIG. 2 in case of rise (R) and 1 ns corresponding to the upper route (arc "a" .fwdarw. "b" .fwdarw. "c" .fwdarw. "d") in FIG. 2 in case of fall (F).
This is because the device 240 is an OR device and the delay time for the signal with rise (R) passing the upper route in FIG. 2 does not have any meaning, or the rise (R) signal for the path 250 (arc "c") has no effect (invalid) on determination of the delay time.
However, the conventional delay time verification method using a verified model does not have any information that the rise (R) signal at the arc "c" does not have any meaning (invalid) for determination of the delay time and processes the signal as valid data (In FIG. 6, a weight of 0 ns is given to R/R of the arc "c"). It is judged here that the delay time of the signal from the upper route in FIG. 2 is meaningful (valid).
Specifically, the delay time is determined for all paths of the circuit model in FIG. 2, so as to obtain the results as shown in FIGS. 12 and 13. As understood from the figures, the delay time of the route in FIG. 12 is 1 ns for both rise and fall. Comparison of FIGS. 12 and 13 shows that the verification results here are different from the actual delay time.